# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/6/5 13:01
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : merge_and_sort.py
@Version     : Version 1.0.0
@Description : TODO
@Created By  : PyCharm
"""


def merge_and_count(a, b):
    """
    统计跨界情况下的逆序数，其中输入序列a,b必须升序排列
    :param a: 升序排列左序列
    :param b: 升序排列右序列
    :return: 跨界情况下的逆序数，升序排列的合并序列
    """
    i, j, inv_count = 0, 0, 0
    merge_list = []
    len_a = len(a)
    len_b = len(b)
    while i < len_a and j < len_b:
        if a[i] < b[j]:
            merge_list.append(a[i])
            i += 1
        else:
            # 由于a[i] > b[j]且a为升序排列，所以包括a[i]及其之后的元素都与 b[j]构成逆序对
            inv_count += len_a - i
            merge_list.append(b[j])
            j += 1
    while i < len_a:
        merge_list.append(a[i])
        i += 1
    while j < len_b:
        merge_list.append(b[j])
        j += 1
    return inv_count, merge_list


if __name__ == '__main__':
    prefer_list = [2, 4, 1, 3, 5]
    al = [2, 4]
    ar = [1, 3, 5]
    print(merge_and_count(al, ar))
